package com.leetcode.algorithm.y22.m06;

/**
 * 576. 出界的路径数
 * 
 * https://leetcode.cn/problems/out-of-boundary-paths/
 * 
 * @author jie.deng
 *
 */
class Question0576Solution01 {

	public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
		if (maxMove == 0) {
			return 0;
		}
		int mod = 1000000007;
		// dp状态定义：dp[k][i][j]表示起始坐标为 [i, j],最多可以移动k次球,可以将球移出边界的路径数量
		int[][][] dp = new int[maxMove + 1][m][n];

		// dp状态初始化
		// k=0,dp[k][i][j]赋值
		// dp[0][i][j]=0

		// k=1,dp[k][i][j]赋值
		for (int i = 0; i < m; i++) {
			// 左边界
			dp[1][i][0] += 1;
			// 右边界
			dp[1][i][n - 1] += 1;
		}
		for (int j = 0; j < n; j++) {
			// 上边界
			dp[1][0][j] += 1;
			// 下边界
			dp[1][m - 1][j] += 1;
		}
		// 其他dp[1][i][j]=0

		// k>=2,dp[k][i][j]赋值
		for (int k = 2; k <= maxMove; k++) {
			for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++) {
					// dp[k][i][j] = dp[k-1][i-1][j] + dp[k-1][i+1][j] + dp[k-1][i][j-1] + dp[k-1][i][j+1]
					if (i >= 1) {
						// 先往上移动一步，然后穿过网格边界
						dp[k][i][j] += dp[k-1][i - 1][j];
						dp[k][i][j] %= mod;
					}
					if (i < m - 1) {
						// 先往下移动一步，然后穿过网格边界
						dp[k][i][j] += dp[k-1][i + 1][j];
						dp[k][i][j] %= mod;
					}
					if (j >= 1) {
						// 先往上移动一步，然后穿过网格边界
						dp[k][i][j] += dp[k-1][i][j - 1];
						dp[k][i][j] %= mod;
					}
					if (j < n - 1) {
						// 先往下移动一步，然后穿过网格边界
						dp[k][i][j] += dp[k-1][i][j + 1];
						dp[k][i][j] %= mod;
					}
					// WARNING 不经过周围节点，直接出界
					if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
						dp[k][i][j] += dp[1][i][j];
						dp[k][i][j] %= mod;
					}
				}
			}
		}
		return dp[maxMove][startRow][startColumn];
	}

}